package com.shuang.greed13;

import java.util.Arrays;

public class EraseOverlapIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {

        //用于记录结果
        int count = 0;

        //对数组按照左边界进行排序
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        //从前向后 遍历排序过的intervals
        for (int i = 1; i < intervals.length; i++) {
            //判断当前位置的气球区间是否和上一个区间重叠
            if (intervals[i][0] < intervals[i - 1][1]) {
                //当前位置的左边界 小于前一个位置的右边界 这两个区间重叠
                //重叠
                count++;
                //更新这两个位置的区间右边界
                intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
            }
        }

        return count;

    }
}
